package com.sheng.leetcode.year2023.month03.day22;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/03/22
 * <p>
 * 1626. 无矛盾的最佳球队<p>
 * <p>
 * 假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。<p>
 * 然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。<p>
 * 如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。<p>
 * 给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。<p>
 * 请你返回 所有可能的无矛盾球队中得分最高那支的分数 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]<p>
 * 输出：34<p>
 * 解释：你可以选中所有球员。<p>
 * <p>
 * 示例 2：<p>
 * 输入：scores = [4,5,6,5], ages = [2,1,2,1]<p>
 * 输出：16<p>
 * 解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。<p>
 * <p>
 * 示例 3：<p>
 * 输入：scores = [1,2,3,5], ages = [8,9,10,1]<p>
 * 输出：6<p>
 * 解释：最佳的选择是前 3 名球员。<p>
 * <p>
 * 提示：<p>
 * 1 <= scores.length, ages.length <= 1000<p>
 * scores.length == ages.length<p>
 * 1 <= scores[i] <= 10^6<p>
 * 1 <= ages[i] <= 1000<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/best-team-with-no-conflicts">1626. 无矛盾的最佳球队</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1626 {

    @Test
    public void test01() {
//        int[] scores = {1, 3, 5, 10, 15}, ages = {1, 2, 3, 4, 5};
//        int[] scores = {4, 5, 6, 5}, ages = {2, 1, 2, 1};
//        int[] scores = {1, 2, 3, 5}, ages = {8, 9, 10, 1};
        int[] scores = {9, 2, 8, 8, 2}, ages = {4, 1, 3, 3, 5};
        System.out.println(new Solution().bestTeamScore(scores, ages));
    }
}

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        // 满足 ages[i] > ages[j] 的情况下必须有 scores[i] > scores[j]
        int n = scores.length;
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = scores[i];
            nums[i][1] = ages[i];
        }
        // 按照分数从小到大排序，分数相等时，按照年龄从小到大排序
        Arrays.sort(nums, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
        // 返回值
        int count = 0;
        // f[i] 代表已 i 队员为结尾时，球队的分数
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i][1] >= nums[j][1]) {
                    f[i] = Math.max(f[i], f[j]);
                }
            }
            f[i] += nums[i][0];
            count = Math.max(count, f[i]);
        }
        return count;
//        for (int i = 0; i < n; i++) {
//            int max = nums[i][0];
//            int index = i;
//            for (int j = i + 1; j < n; j++) {
//                if (nums[j][1] >= nums[index][1]) {
//                    max += nums[j][0];
//                    index = j;
//                }
//            }
//            count = Math.max(max, count);
//        }
//        return count;
    }
}
